package no57;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/6/11 23:59
 * 剑指 offer 57-II 和为 s 的连续正数序列
 * https://leetcode.cn/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/
 */
public class Solution02 {

    // 滑动窗口 时间复杂度 O(n)
    public int[][] findContinuousSequence(int target) {
        int i = 1; // 滑动窗口的左边界
        int j = 1; // 滑动窗口的右边界
        int sum = 0; // 滑动窗口中数字的和
        List<int[]> res = new ArrayList<>();

        while (i <= target / 2) {
            if (sum < target) {
                // 右边界向右移动
                sum += j;
                j++;
            } else if (sum > target) {
                // 左边界向右移动
                sum -= i;
                i++;
            } else {
                // 记录结果
                int[] arr = new int[j-i];
                for (int k = i; k < j; k++) {
                    arr[k-i] = k;
                }
                res.add(arr);
                // 左边界向右移动
                sum -= i;
                i++;
            }
        }

        return res.toArray(new int[res.size()][]);
    }

    public static void main(String[] args) {
        int target = 9;
        int[][] sequence = new Solution02().findContinuousSequence(target);
        for (int i = 0; i < sequence.length; i++) {
            System.out.println(Arrays.toString(sequence[i]));
        }
    }
}
